package sjjg.graph;

public class DirectedCycle {
    private boolean[]marked;//用来标识某个节点是否完成搜索
    private boolean[]onStack;//用来记录某次深度遍历一些元素的遍历情况 (通过栈的思想来检测是否存在环 如果本次某个元素进入到遍历那么相当于这个元素在栈中)
    private boolean hasCycle;
    DirectedCycle(Digraph digraph){
          if(digraph==null){
              return;
          }
            hasCycle=false;
            marked=new boolean[digraph.V()];
            onStack=new boolean[digraph.V()];
            //对每个节点都进行搜索
        for (int v = 0; v < digraph.V(); v++) {
            if(hasCycle){
                return;
            }
             if(!marked[v]){//如果已经搜索过程中被搜索过就没必要再搜索了
                 dfs(digraph,v);
             }
        }
    }
    private void dfs(Digraph digraph,int v){//深度优先遍历探测digraph是否有环
                //标识v已被深度搜索
                marked[v]=true;
               //节点v入栈 标识该节点进入这次搜索栈中
               onStack[v]=true;
              //递归调用方法实现深度优先遍历
        for (Integer w : digraph.adj(v)) {
            if(!marked[w]){
                dfs(digraph,w);
            }
            if(onStack[w]){
                hasCycle=true;
                return;
            }
        }
        //某个节点的深度优先遍历结束 让该节点退出本次遍历栈
        onStack[v]=false;
    }
    public boolean hasCycle(){
        return hasCycle;
    }
    public static void main(String[] args) {
        Digraph digraph = new Digraph(6);
        digraph.addEdge(0,1);
        digraph.addEdge(1,2);
        digraph.addEdge(2,3);
        digraph.addEdge(3,4);
        digraph.addEdge(4,5);
        digraph.addEdge(5,2);
        DirectedCycle directedCycle = new DirectedCycle(digraph);
        boolean b = directedCycle.hasCycle();
        if(b){
            System.out.println("has");
        }else {
            System.out.println("no");
        }
    }
}
